package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Backtracking;
import cn.pugle.oj.catalog.TreeProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.*;

/**
 * https://leetcode.com/problems/word-ladder/solution/
 * 广度优先, 最先看到的解法是深度最小的, 直接返回
 * 和回溯有点像
 *
 * @author tzp
 * @since 2020/11/4
 */
public class LC127_3 implements TreeProblem, Backtracking {
    class Pair<A, B> {
        A a;
        B b;

        public Pair(A a, B b) {
            this.a = a;
            this.b = b;
        }

        public A getKey() {
            return a;
        }

        public B getValue() {
            return b;
        }
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int L = beginWord.length();//all words are of same length.

        // Dictionary to hold combination of words that can be formed from any given word.
        // By changing one letter to * at a time.
        // 注意 这块秀了!!  key是带*的中介word, v是对应的words
        Map<String, List<String>> allComboDict = new HashMap<>();
        wordList.forEach(
                word -> {
                    for (int i = 0; i < L; i++) {
                        // Key is the generic word
                        // Value is a list of words which have the same intermediate generic word.
                        String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
                        List<String> transformations = allComboDict.getOrDefault(newWord, new ArrayList<>());
                        transformations.add(word);
                        allComboDict.put(newWord, transformations);
                    }
                });

        // Queue for BFS
        Queue<Pair<String, Integer>> Q = new LinkedList<>();//pair: Word, Level
        Q.add(new Pair(beginWord, 1));

        // Visited记录下, 以免重复进入死循环
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);

        while (!Q.isEmpty()) {
            Pair<String, Integer> node = Q.remove();
            String word = node.getKey();
            int level = node.getValue();
            for (int i = 0; i < L; i++) {//广度优先, 这两个循环对应着每个子分叉.
                // Intermediate words for current word
                String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
                // Next states are all the words which share the same intermediate state.
                for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {
                    // If at any point if we find what we are looking for - we can return with the answer.
                    if (adjacentWord.equals(endWord)) {
                        return level + 1;
                    }
                    // Otherwise, add it to the BFS Queue. Also mark it visited
                    if (!visited.contains(adjacentWord)) {
                        visited.add(adjacentWord);
                        Q.add(new Pair(adjacentWord, level + 1));
                    }
                }
            }
        }

        return 0;
    }

}
